import java.util.ArrayList;
import java.util.List;

public class Solution {
    public List<List<Integer>> generate(int numRows){
        List<List<Integer>> triangle=new ArrayList<>();
        for (int i = 0; i < numRows; i++) {
            List<Integer> row=new ArrayList<>();
            for (int j = 0; j < i; j++) {
                if(j==1||j==i){
                    row.add(1);
                }else{
                    int num=triangle.get(i-1).get(j-1)+triangle.get(i-1).get(j);
                    row.add(num);
                }
            }
            triangle.add(row);
        }
        return triangle;
    }


    public class ListNode {
        int val;
        ListNode next = null;

        ListNode(int val) {
            this.val = val;
        }
    }
    public class Partition {
        public ListNode partition(ListNode pHead, int x) {
            // write code here
            ListNode ba=null;
            ListNode be=null;
            ListNode sa=null;
            ListNode se=null;
            if(pHead==null){
                return pHead;
            }
            ListNode cur=pHead;
            while (cur!=null){
                if(cur.val<=x){
                    if(ba==null){
                        ba=cur;
                        be=cur;

                    }else{
                        be.next=cur ;
                        be=cur;

                    }
                }else {
                    if(sa==null){
                        sa=cur;
                        se=cur;

                    }else{
                        se.next=cur;
                        se=cur;

                    }
                }
                cur=cur.next;
            }

            if(se!=null){
                se.next=null;
            }
            if(be==null){
                return sa;
            }
            be.next=sa;
            return ba;
        }
    }
}
